package com.graph.impl;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import Jama.Matrix;

import com.graph.base.Edge;
import com.graph.base.GraphBase;
import com.graph.base.GraphInterface;
import com.graph.base.VertexInterface;
import com.graph.util.GraphFileUtils;

public class ProbabilityModelGraph extends GraphBase implements GraphInterface{
	public static final String DATA_PATH=".\\Data\\";
	public static final String FILE_NAME="graph2.txt";
	private  Integer N;
	private  double  P;
	private  double  M;
	
	
	/**
	 * @Description:TODO
	 * @param args
	 * @author: wujiang
	 * @time:2017-1-12 上午10:49:35
	 */
	public static void main(String[] args) {
		ProbabilityModelGraph pro=new ProbabilityModelGraph(4,0.5,2);
		Map<Matrix,Integer> mres=pro.clustering();
		Set<Matrix> mas=mres.keySet();
		Iterator<Matrix> it=mas.iterator();
		while(it.hasNext()){
			Matrix m=it.next();
			Integer w=mres.get(m);
			System.out.println("权值："+w);
			for (int i = 0; i < pro.N; i++) {
				for (int j = 0; j < pro.N; j++) {
				System.out.print(m.get(i, j)+" ");
				}
				System.out.println();
			}
		}
//		for (List<VertexInterface<String>> vertexInterfaces : res) {
//			for (VertexInterface<String> vertexInterface : vertexInterfaces) {
//				System.out.print(vertexInterface.getName()+"、");
//			}
//			System.out.println();
//		}
	}
	
	public ProbabilityModelGraph(Integer N, double P,double M) {
		this.M=M;
		this.N=N;
		this.P=P;
		GraphFileUtils.getInstance().read(DATA_PATH, FILE_NAME,this);
	}
    public  Map<Matrix,Integer> clustering(){
    	 Map<Matrix,Integer> RRES=new LinkedHashMap<Matrix, Integer>();
    	LinkedList<Double> M=new  LinkedList<Double>();  
    	Map<List<VertexInterface>,Matrix> PALM=new LinkedHashMap<List<VertexInterface>, Matrix>();
    	LinkedList<List<List<VertexInterface>>> PALL=new LinkedList<List<List<VertexInterface>>>();
    	Map<List<VertexInterface>,Integer>	childrenGraph=initChildrenGraph(N,P);
    	List<List<VertexInterface>> keys=new ArrayList<List<VertexInterface>>(childrenGraph.keySet());
    	for (int i = 0; i < keys.size(); i++) {
			for (int j = 0; j < keys.size(); j++) {
				List<VertexInterface> g1=keys.get(i);
				List<VertexInterface> g2=keys.get(j);
				if(i!=j){
					Matrix mat1=getMatrixByGraph(g1);
					Matrix mat2=getMatrixByGraph(g2);
					double mis=misMatch(mat1,mat2);
					if(mis<=this.M){
					List<List<VertexInterface>> pair=new LinkedList<List<VertexInterface>>();
					pair.add(g1);
					pair.add(g2);
					PALM.put(g1, mat1);
					PALM.put(g2, mat2);
						if(M.size()==0){
							M.add(mis);
							PALL.add(pair);
						}else{
						for (int k = 0; k < M.size(); k++) {
							if(M.get(k)>=mis){
								M.add(k, mis);
								PALL.add(k,pair);
								break;
							}
						}
						}
					}
				}
			}
		}
		
		while(PALL.size()>0){
			List<List<VertexInterface>> pairL=PALL.get(0);
			List<VertexInterface> gL1=pairL.get(0);
			List<VertexInterface> gL2=pairL.get(1);
			Set<VertexInterface> setPair=new HashSet<VertexInterface>();
			setPair.addAll(gL1);
			setPair.addAll(gL2);
			if(setPair.size()>N){
				Integer w1=childrenGraph.remove(gL1);
				Integer w2=childrenGraph.remove(gL2);
				if(w1==null||w2==null){
					PALL.remove();
					continue;
					}
				Matrix mat1=PALM.get(gL1);
				Matrix mat2=PALM.get(gL2);
				List<VertexInterface>  newGl=new ArrayList<VertexInterface>(setPair);
				Matrix matR= getNewMatrix(mat1,w1,mat2,w2);
				PALM.put(newGl,matR);
				List<List<VertexInterface>> keys2=new ArrayList<List<VertexInterface>>(childrenGraph.keySet());
				for (int i = 0; i < childrenGraph.size(); i++) {
						List<VertexInterface> t1=keys2.get(i);
						Matrix mat6=null;
						if(t1.size()==N){
							mat6=getMatrixByGraph(t1);
						}else{
							mat6=PALM.get(t1);
						}
						double mis=misMatch(mat6,matR);
						if(mis<=this.M){	
							List<List<VertexInterface>> pairT=new LinkedList<List<VertexInterface>>();
							pairT.add(t1);
							pairT.add(newGl);
								if(M.size()==0){
									M.add(mis);
									PALL.add(pairT);
								}else{
								for (int k = 0; k < M.size(); k++) {
									if(M.get(k)>mis){
										M.add(k, mis);
										PALL.add(k,pairT);
										break;
									}
								}
								}
						}
				}
				PALL.remove();
				childrenGraph.put(newGl,w1+w2);
			}else{
				continue;
			}
			
		}
		ArrayList<List<VertexInterface>> re = new ArrayList<List<VertexInterface>>(childrenGraph.keySet());
		for (List<VertexInterface> list : re) {
			RRES.put(PALM.get(list),childrenGraph.get(list));
		}
    	return RRES;
    }
    
    
    public  List<Set<VertexInterface>> clustering1(){
   	 Map<Matrix,Integer> RRES=new LinkedHashMap<Matrix, Integer>();
   	LinkedList<Double> M=new  LinkedList<Double>();  
   	Map<List<VertexInterface>,Matrix> PALM=new LinkedHashMap<List<VertexInterface>, Matrix>();
   	LinkedList<List<List<VertexInterface>>> PALL=new LinkedList<List<List<VertexInterface>>>();
   	Map<List<VertexInterface>,Integer>	childrenGraph=initChildrenGraph(N,P);
   	List<List<VertexInterface>> keys=new ArrayList<List<VertexInterface>>(childrenGraph.keySet());
   	for (int i = 0; i < keys.size(); i++) {
			for (int j = 0; j < keys.size(); j++) {
				List<VertexInterface> g1=keys.get(i);
				List<VertexInterface> g2=keys.get(j);
				if(i!=j){
					Matrix mat1=getMatrixByGraph(g1);
					Matrix mat2=getMatrixByGraph(g2);
					double mis=misMatch(mat1,mat2);
					if(mis<=this.M){
					List<List<VertexInterface>> pair=new LinkedList<List<VertexInterface>>();
					pair.add(g1);
					pair.add(g2);
					PALM.put(g1, mat1);
					PALM.put(g2, mat2);
						if(M.size()==0){
							M.add(mis);
							PALL.add(pair);
						}else{
						for (int k = 0; k < M.size(); k++) {
							if(M.get(k)>=mis){
								M.add(k, mis);
								PALL.add(k,pair);
								break;
							}
						}
						}
					}
				}
			}
		}
		
		while(PALL.size()>0){
			List<List<VertexInterface>> pairL=PALL.get(0);
			List<VertexInterface> gL1=pairL.get(0);
			List<VertexInterface> gL2=pairL.get(1);
			Set<VertexInterface> setPair=new HashSet<VertexInterface>();
			setPair.addAll(gL1);
			setPair.addAll(gL2);
			if(setPair.size()>N){
				Integer w1=childrenGraph.remove(gL1);
				Integer w2=childrenGraph.remove(gL2);
				if(w1==null||w2==null){
					PALL.remove();
					continue;
					}
				Matrix mat1=PALM.get(gL1);
				Matrix mat2=PALM.get(gL2);
				List<VertexInterface>  newGl=new ArrayList<VertexInterface>(setPair);
				Matrix matR= getNewMatrix(mat1,w1,mat2,w2);
				PALM.put(newGl,matR);
				List<List<VertexInterface>> keys2=new ArrayList<List<VertexInterface>>(childrenGraph.keySet());
				for (int i = 0; i < childrenGraph.size(); i++) {
						List<VertexInterface> t1=keys2.get(i);
						Matrix mat6=null;
						if(t1.size()==N){
							mat6=getMatrixByGraph(t1);
						}else{
							mat6=PALM.get(t1);
						}
						double mis=misMatch(mat6,matR);
						if(mis<=this.M){	
							List<List<VertexInterface>> pairT=new LinkedList<List<VertexInterface>>();
							pairT.add(t1);
							pairT.add(newGl);
								if(M.size()==0){
									M.add(mis);
									PALL.add(pairT);
								}else{
								for (int k = 0; k < M.size(); k++) {
									if(M.get(k)>mis){
										M.add(k, mis);
										PALL.add(k,pairT);
										break;
									}
								}
								}
						}
				}
				PALL.remove();
				childrenGraph.put(newGl,w1+w2);
			}else{
				continue;
			}
			
		}
		ArrayList<Set<VertexInterface>> re = new ArrayList<Set<VertexInterface>>();
		Set<List<VertexInterface>> keysets=childrenGraph.keySet();
		Iterator<List<VertexInterface>>it= keysets.iterator();
		while (it.hasNext()) {
			List<VertexInterface> list = (List<VertexInterface>) it.next();
			re.add(new HashSet<VertexInterface>(list));
		}
   	return re;
   }
    
    
    
    private Matrix getNewMatrix(Matrix Ma1,Integer w1,Matrix Ma2, Integer w2){
    	double[][] t=new double[N][N];
    	for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				t[i][j]=(Ma1.get(i, j)*w1+Ma2.get(i, j)*w2)/(w1+w2);
			}
		}
		return new Matrix(t);
    }
    
    private Matrix getMatrixByGraph(List<VertexInterface> g){
    	double[][] t=new double[N][N]; 
    	for (int i = 0; i < g.size(); i++) {
    		Set<VertexInterface> nes=getNeighbors(g.get(i));
    		t[i][i]=0;
			for (int j = i+1; j < g.size(); j++) {
				if(nes.contains(g.get(j))){
					t[i][j]=t[j][i]=1;
				}else{
				    t[i][j]=t[j][i]=0;
				}
			}
		}
    	Matrix tM=new Matrix(t);
		return tM;
    }
    
    private double misMatch(Matrix t1,Matrix t2){
    	LinkedList<Integer> initMat=new LinkedList<Integer>();
    	for (int i = 0; i < N; i++) {
			initMat.add(i);
		}
    	List<LinkedList<Integer>> mats =new ArrayList<LinkedList<Integer>>();
    	AllMat(mats,initMat,null,N);
    	double mis=100;
    	double tmis=0;
    	double[][] t=new double[N][N];
    	Matrix tM=new Matrix(t);
    	for (int i = 0; i < mats.size(); i++) {
    		LinkedList<Integer> matT=mats.get(i);
    		int[] tl=new int[matT.size()];
			for (int j = 0; j < N; j++) {
				tl[j]=matT.pollFirst();
			}
			for (int j2 = 0; j2 < tl.length; j2++) {
			   for (int j3 = 0; j3 < tl.length; j3++) {
				tmis+=(1-t1.get(tl[j2], tl[j3]))*t2.get(j2,j3);
				tmis+=(1-t2.get(j2, j3))*t1.get(tl[j2],tl[j3]);
				tM.set(tl[j2],tl[j3],t1.get(j2,j3));
			   }	
			}
			if(mis>tmis){
				mis=tmis;
				t1=tM;
			}
		}
    	return mis;
    }
    private void AllMat(List<LinkedList<Integer>> mats,LinkedList<Integer> eles,LinkedList<Integer> pre,Integer n){
    	if(pre==null){
    		pre=new LinkedList<Integer>();
    	}
    	for(int i=0;i<eles.size();i++){
    		LinkedList<Integer> Npre=new LinkedList<Integer>(pre);
    		Npre.addLast(eles.get(i));
    		if(Npre.size()==n){
    			mats.add(Npre);
    		}else{
    		LinkedList<Integer> Neles=new LinkedList<Integer>(eles); 
    		Neles.remove(i);
    		AllMat(mats,Neles, Npre,n);
    		
    		}
    	}
    }
    
    
    
    
  public Map<List<VertexInterface>,Integer> initChildrenGraph(int n,double p){
		Map<List<VertexInterface>,Integer> result=new LinkedHashMap<List<VertexInterface>, Integer>();
		this.n=n;
  	List<VertexInterface> V=new ArrayList<VertexInterface>();
  	Map<String, VertexInterface> vesTotall = getVertices();
  	V.addAll(vesTotall.values());
  	GraphFileUtils utils=GraphFileUtils.getInstance();
  	utils.sortAndCode(V);
  	while(V.size()>0){
  		List<List<VertexInterface>> childrenGraphs=new ArrayList<List<VertexInterface>>();
  		VertexInterface seed=V.get(0);
  		if(seed!=null){
  			findChildrenGraph(null,null,seed,n,childrenGraphs);
  			if(childrenGraphs.size()>0){
  				for (List<VertexInterface> list : childrenGraphs) {
//      				if(isComCodeGraph(list)){
//      					continue;
//      				}
  					List<Edge> edges=getEdge(list);
      				Integer edgeNum=0;
      				if(edges.size()>0){
      					edgeNum=edges.size()/2;
      				Integer vertexNum=childrenGraphs.size();
      				if(getNumberOfEdges()>vertexNum&&childrenP(list,getNumberOfEdges())>p){
                           
      					
      					Boolean isContain=false;
//      					Set<List<VertexInterface<T>>> setT=result.keySet();
//      					for (List<VertexInterface<T>> list2 : setT) {
//								if(list2.containsAll(list)){
//									isContain=true;
//									Integer w=result.get(list2);
//									result.put(list2, w+1);
//									break;
//								}
//							}
      					if(isContain==false){
      					result.put(list, 1);
      					}
//      					addResultCode(list);
      				}
      				}
					}
  			}
  			removeVertex(V,seed);
  		}
  	}
  	return result;
  }
  
	
	private void removeVertex(List<VertexInterface> result,
			VertexInterface seed) {
		Set<VertexInterface>  negihbors=getNeighbors(seed);
		for (VertexInterface vertexInterface : negihbors) {
			if(vertexInterface.getEdgeList().size()==1){
				result.remove(vertexInterface);
			}
		}
		result.remove(seed);
	}
  
  
	private Integer n=N;
	private void findChildrenGraph(Set<VertexInterface> lastChildrenGraph,List<VertexInterface> around,VertexInterface seed,Integer k,List<List<VertexInterface>> childrenGraphs){
		if(lastChildrenGraph==null){
			lastChildrenGraph=new HashSet<VertexInterface>();
			lastChildrenGraph.add(seed);
		}
		k--;
		if(around==null){
		 around=getNeighborsByNumber(seed);
		}
		List<VertexInterface> tempAround=new ArrayList<VertexInterface>();
		tempAround.addAll(around);
		while(around.size()>0){
			VertexInterface tem=around.remove(0);
			Set<VertexInterface> temCh=new HashSet<VertexInterface>(lastChildrenGraph);
			temCh.add(tem);
			if(k==1){
				List<VertexInterface> ch=new ArrayList<VertexInterface>(temCh);
				if(ch.size()==n)
				childrenGraphs.add(ch);
			}else{
				List<VertexInterface> ex=new ArrayList<VertexInterface>(around);
				Iterator<VertexInterface> iter=tem.getNeighborInterator();
				while(iter.hasNext()){
					VertexInterface temp=iter.next();
					if(temp.getReNumber()>tem.getReNumber()&&!tempAround.contains(temp)&&!lastChildrenGraph.contains(temp))
						ex.add(temp);
				}
				findChildrenGraph(temCh, ex, seed, k, childrenGraphs);
			}
		}
//		
//		
//      for (VertexInterface<T> tem : around) {
//      	Set<VertexInterface<T>> nowChildren=new HashSet<VertexInterface<T>>();
//      	nowChildren.addAll(lastChildrenGraph);
//      	nowChildren.add(tem);
//      	if(k>=1){
//      		List<VertexInterface<T>> list=new ArrayList<VertexInterface<T>>(nowChildren);
//      		childrenGraphs.add(list);
//  		}else{
//  			findChildrenGraph(nowChildren,around,tem,k,childrenGraphs);
//  		}
//      	
//		}
//
//		
		
	
	}
  

	
	private List<VertexInterface>  getNeighborsByNumber(VertexInterface aim){
		List<VertexInterface> around=new ArrayList<VertexInterface>();
		Iterator<VertexInterface> iter=aim.getNeighborInterator();
		while(iter.hasNext()){
			VertexInterface temp=iter.next();
			if(temp.getReNumber()>aim.getReNumber())
			around.add(temp);
		}
		return around;
	}
	
	

	private double childrenP(List<VertexInterface> G,Integer edgeNum){
		double resut=0;
		for (VertexInterface vertexInterface0 : G) {
			List<VertexInterface> aroundVertex=new ArrayList<VertexInterface>();
			List<Edge>  aroundEdges=vertexInterface0.getEdgeList();
			double d0=aroundEdges.size();
			for (Edge edge : aroundEdges) {
				aroundVertex.add(edge.getEndVertex());
			}
			for (VertexInterface vertexInterface1 : G) {
				double d1=vertexInterface1.getEdgeList().size();
				if(aroundVertex.contains(vertexInterface1)){
					resut+=(d0*d1)/edgeNum;
				}else{
					resut+=1-((d0*d1)/edgeNum);
				}
			}
		}
		
		return resut;
	}

	@Override
	public Set<VertexInterface> findCommunityByVertices(String ver)
			throws Exception {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public List<Set<VertexInterface>> findAllCommunity() throws Exception {
		return (List<Set<VertexInterface>>) clustering1();
	}

	@Override
	public List<VertexInterface> getBoundaryVertices() throws Exception {
		// TODO Auto-generated method stub
		return null;
	}


	@Override
	public int[][] initMatrix() throws Exception {
		return new int[0][];
	}

	@Override
	public double getPrecision() {
		return 0;
	}

	@Override
	public double getRecall() {
		return 0;
	}

	@Override
	public double getF1() {
		return 0;
	}
}
